/**
 * @file 手中有N个长度为D的树枝，有一天，心血来潮，把N根树枝切成了M个不等长的树枝，之后石老板企图重新把这M个不等长的树枝，拼回去，却发现自己忘记了N和D，请问，再保证D最小的情况下，求出之前的N个树枝的长度D
 * @author
 */

// 剪枝
let loopCount = 0;

const search = (sticks, originStickLen, index, curStickLen, visited) => {

    if (visited.every(item => item === 1) && curStickLen === 0) {
        return true;
    }

    let cursor = -1;
    for (let i = 0, len = sticks.length; i < len; i++) {

        loopCount++;

        if (visited[i] === 1 || cursor === sticks[i]) {
            continue;
        }

        visited[i] = 1;

        if (curStickLen + sticks[i] < originStickLen) {
            if (search(sticks, originStickLen, i, curStickLen + sticks[i], visited)) {
                return true;
            }
            cursor = sticks[i];
        }
        else if (curStickLen + sticks[i] === originStickLen) {
            if (search(sticks, originStickLen, i, 0, visited)) {
                return true;
            }
            cursor = sticks[i];
        }

        visited[i] = 0;

        if (curStickLen === 0) {
            break;
        }
    }

    return false;

}

const start = () => {
    // M -> N D
    let sticks = [1, 3, 2, 4, 2, 2, 5, 2, 3, 4, 2, 5, 2, 5].sort((a, b) => b - a);

    let sum = eval(sticks.join('+'));

    // 枚举所有的原始棍长可能性
    for (let originStickLen = sticks[0]; originStickLen < sum; originStickLen++) {
        const visited = Array(sticks.length).fill(0);
        if ((sum % originStickLen === 0) &&  search(sticks, originStickLen, 0, 0, visited)) {
            console.log('originStickLen:::', originStickLen, loopCount);
            return;
        }
    }

    console.log('没有搜索到');
};

start();
